package leetcode.easy.q101;

import leetcode.util.TreeNode;
import leetcode.util.Utils;
import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

@Slf4j
public class Q {
    public static void main(String[] args) {
        log.info("res:{}",new Solution().isSymmetric(Utils.buildTree(1,2,2,3,4,4,3)));
        log.info("res:{}",new Solution().isSymmetric(Utils.buildTree(1,2,2,null,3,null,3)));
        log.info("res:{}",new Solution().isSymmetric2(Utils.buildTree(1,2,2,3,4,4,3)));
        log.info("res:{}",new Solution().isSymmetric2(Utils.buildTree(1,2,2,null,3,null,3)));
    }
}


class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root.left, root.right);
    }
    /**
     * 参考q100,比较两棵相同的树，此时只需要左子树与右子树比较
     */
    public boolean isSymmetric(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        } else if (p.val == q.val) {
            return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
        }
        return false;
    }

    /**
     * 基于栈，循环比较
     * @param root
     * @return
     */
    public boolean isSymmetric2(TreeNode root) {
        Stack<TreeNode> left = new Stack<>();
        Stack<TreeNode> right = new Stack<>();
        left.push(root.left);
        right.push(root.right);
        while (!left.isEmpty() && !right.isEmpty()) {
            TreeNode l = left.pop();
            TreeNode r = right.pop();
            if (l == null && r == null) {
                continue;
            }
            if (l == null || r == null) {
                return false;
            }
            if (l.val != r.val) {
                return false;
            } else {
                left.push(l.left);
                left.push(l.right);
                right.push(r.right);
                right.push(r.left);
            }
        }
        return true;
    }

}